﻿using System;
using System.Collections.Generic;

namespace IceCS.DataStructure.Core.BinaryTree
{
    /// <summary>
    /// 树遍历方式
    /// </summary>
    public enum TreeSearchOrderType
    {
        /// <summary>
        /// 先序遍历
        /// </summary>
        Preorder = 1,
        /// <summary>
        /// 中序遍历
        /// </summary>
        Inorder,
        /// <summary>
        /// 后序遍历
        /// </summary>
        Postorder,
        /// <summary>
        /// 层次遍历
        /// </summary>
        Levelorder,
    }

    /// <summary>
    /// 链式二叉树
    /// </summary>
    /// <typeparam name="T"></typeparam>
    public class LinkBTree<T>//:IBTree<T>
    {
        /// <summary>
        /// 头结点
        /// </summary>
        public BTreeNode<T> Head { get; set; }

        /// <summary>
        /// 判断树是否为空
        /// </summary>
        public bool IsEmpty => Head == null;

        /// <summary>
        /// 构造函数
        /// </summary>
        public LinkBTree()
        {
            Head = null;
        }

        /// <summary>
        /// 构造函数
        /// </summary>
        /// <param name="headData">头节点数据</param>
        public LinkBTree(T headData)
        {
            Head = new BTreeNode<T>(headData);
        }

        /// <summary>
        /// 构造函数
        /// </summary>
        /// <param name="headData">头节点数据</param>
        /// <param name="leftChildNode">左子节点</param>
        /// <param name="rightChildNode">右子节点</param>
        public LinkBTree(T headData, BTreeNode<T> leftChildNode, BTreeNode<T> rightChildNode)
        {
            Head = new BTreeNode<T>(headData, leftChildNode, rightChildNode);
        }

        /// <summary>
        /// 获取根节点
        /// </summary>
        /// <returns></returns>
        public BTreeNode<T> GetRoot()
        {
            return Head;
        }

        /// <summary>
        /// 获取左子节点
        /// </summary>
        /// <param name="node">传入的节点</param>
        /// <returns></returns>
        public BTreeNode<T> GetLeftChildNode(BTreeNode<T> node)
        {
            return node.LeftChildNode;
        }

        /// <summary>
        /// 获取右子节点
        /// </summary>
        /// <param name="node">传入的节点</param>
        /// <returns></returns>
        public BTreeNode<T> GetRightChildNode(BTreeNode<T> node)
        {
            return node.RightChildNode;
        }

        /// <summary>
        /// 插入左子节点,后插方式
        /// </summary>
        /// <param name="node">传入的节点</param>
        /// <param name="data">新节点数据</param>
        public void InsertLeftChildNode(BTreeNode<T> node, T data)
        {
            var newNode = new BTreeNode<T>(data);
            var oldLeftNode = node.LeftChildNode;
            node.LeftChildNode = newNode;
            newNode.ParentNode = node;
            newNode.LeftChildNode = oldLeftNode;
            if (oldLeftNode != null)
            {
                oldLeftNode.ParentNode = newNode;
            }
        }

        /// <summary>
        /// 插入左子节点,后插方式
        /// </summary>
        /// <param name="node">传入的节点</param>
        /// <param name="newLeftChildNode">左子节点</param>
        public void InsertLeftChildNode(BTreeNode<T> node, BTreeNode<T> newLeftChildNode)
        {
            var oldLeftNode = node.LeftChildNode;
            node.LeftChildNode = newLeftChildNode;
            newLeftChildNode.ParentNode = node;
            newLeftChildNode.LeftChildNode = oldLeftNode;
            if (oldLeftNode != null)
            {
                oldLeftNode.ParentNode = newLeftChildNode;
            }
        }

        /// <summary>
        /// 插入右子节点,后插方式
        /// </summary>
        /// <param name="node">传入的节点</param>
        /// <param name="data">新节点数据</param>
        public void InsertRightChildNode(BTreeNode<T> node, T data)
        {
            var newNode = new BTreeNode<T>(data);
            var oldRightNode = node.RightChildNode;
            node.RightChildNode = newNode;
            newNode.ParentNode = node;
            newNode.RightChildNode = oldRightNode;
            if (oldRightNode != null)
            {
                oldRightNode.ParentNode = oldRightNode;
            }
        }

        /// <summary>
        /// 插入右子节点,后插方式
        /// </summary>
        /// <param name="node">传入的节点</param>
        /// <param name="newRightChildNode">新节点数据</param>
        public void InsertRightChildNode(BTreeNode<T> node, BTreeNode<T> newRightChildNode)
        {
            var oldRightNode = node.RightChildNode;
            node.RightChildNode = newRightChildNode;
            newRightChildNode.ParentNode = node;
            newRightChildNode.RightChildNode = oldRightNode;
            if (oldRightNode != null)
            {
                oldRightNode.ParentNode = oldRightNode;
            }
        }

        /// <summary>
        /// 删除左子节点
        /// </summary>
        /// <param name="node">传入的节点</param>
        /// <returns></returns>
        public BTreeNode<T> DeleteLeftChildNode(BTreeNode<T> node)
        {
            if (node == null || node.LeftChildNode == null)
            {
                return null;
            }
            var leftChildNode = node.LeftChildNode;
            leftChildNode.ParentNode = null;
            node.LeftChildNode = null;
            return leftChildNode;
        }

        /// <summary>
        /// 删除右子节点
        /// </summary>
        /// <param name="node">传入的节点</param>
        /// <returns></returns>
        public BTreeNode<T> DeleteRightChildNode(BTreeNode<T> node)
        {
            if (node == null || node.RightChildNode == null)
            {
                return null;
            }
            var rightChildNode = node.RightChildNode;
            rightChildNode.ParentNode = null;
            node.RightChildNode = null;
            return rightChildNode;
        }

        /// <summary>
        /// 是否是叶子节点
        /// </summary>
        /// <param name="node">传入的节点</param>
        /// <returns></returns>
        public bool IsLeaf(BTreeNode<T> node) => node.IsLeaf;

        /// <summary>
        /// 在二叉树中查找节点
        /// </summary>
        /// <param name="node">传入的节点</param>
        /// <param name="predicate">判断条件</param>
        /// <param name="searchOrderType">搜索遍历方式</param>
        /// <param name="left2right">是否从左往右遍历，反之则从右到左</param>
        /// <returns></returns>
        public BTreeNode<T> Search(BTreeNode<T> node, Func<BTreeNode<T>, bool> predicate, 
            TreeSearchOrderType searchOrderType = TreeSearchOrderType.Levelorder, bool left2right = true)
        {
            if (node == null)
            {
                return null;
            }

            if (predicate(node))
            {
                return node;
            }

            if (node.LeftChildNode != null)
            {
                return Search(node.LeftChildNode, predicate);
            }

            if (node.RightChildNode != null)
            {
                return Search(node.RightChildNode, predicate);
            }

            return null;
        }

        /// <summary>
        /// 先序遍历
        /// </summary>
        /// <param name="node">要遍历的节点</param>
        /// <param name="action">遍历每个节点的动作</param>
        /// <param name="left2right">是否从左往右遍历，反之则从右到左</param>
        public void PreorderTraversal(BTreeNode<T> node, Action<BTreeNode<T>> action, bool left2right = true)
        {
            if (IsEmpty || node == null)
            {
                return;
            }
            action(node);
            InorderTraversal(node.LeftChildNode, action);
            InorderTraversal(node.RightChildNode, action);
        }

        /// <summary>
        /// 中序遍历
        /// </summary>
        /// <param name="node">要遍历的节点</param>
        /// <param name="action">遍历每个节点的动作</param>
        /// <param name="left2right">是否从左往右遍历，反之则从右到左</param>
        public void InorderTraversal(BTreeNode<T> node, Action<BTreeNode<T>> action, bool left2right = true)
        {
            if (IsEmpty || node == null)
            {
                return;
            }

            InorderTraversal(node.LeftChildNode, action);
            action(node);
            InorderTraversal(node.RightChildNode, action);
        }

        /// <summary>
        /// 后序遍历
        /// </summary>
        /// <param name="node">要遍历的节点</param>
        /// <param name="action">遍历每个节点的动作</param>
        /// <param name="left2right">是否从左往右遍历，反之则从右到左</param>
        public void PostorderTraversal(BTreeNode<T> node, Action<BTreeNode<T>> action, bool left2right = true)
        {
            if (IsEmpty || node == null)
            {
                return;
            }

            InorderTraversal(node.LeftChildNode, action);
            InorderTraversal(node.RightChildNode, action);
            action(node);
        }

        /// <summary>
        /// 层次遍历
        /// </summary>
        /// <param name="node">要遍历的节点</param>
        /// <param name="action">遍历每个节点的动作</param>
        /// <param name="left2right">是否从左往右遍历，反之则从右到左</param>
        public void LevelorderTraversal(BTreeNode<T> node, Action<BTreeNode<T>> action, bool left2right = true)
        {
            if (IsEmpty)
            {
                return;
            }
            Queue<BTreeNode<T>> queue = new Queue<BTreeNode<T>>(50);
            queue.Enqueue(node);
            while (queue.Count > 0)
            {
                var tmpNode = queue.Dequeue();
                action(tmpNode);
                if (tmpNode.LeftChildNode != null)
                {
                    queue.Enqueue(tmpNode.LeftChildNode);
                }
                if (tmpNode.RightChildNode != null)
                {
                    queue.Enqueue(tmpNode.RightChildNode);
                }
            }
        }
    }
}
